package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-08 15:26
 */
public class n_13 {
    public static void main(String[] args) {
        n_13 n = new n_13();
//        int sum = n.getSum(34);
//        System.out.println(sum);
        int res = n.movingCount2(7, 11, 11);
        System.out.println(res);
    }

    public int count = 0;
    public int rows = 0;
    private int cols = 0;

    /**
     *注意：以参数7，11，11为例，虽然（5，10）满足<7,但是，当它到（5，2）之后就不能再往右走了
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public int movingCount(int threshold, int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        boolean[][] isVisited = new boolean[rows][cols];
        helper(threshold, 0, 0, isVisited);
        return count;
    }

    public void helper(int threshold, int r, int c, boolean[][] isVisited) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || isVisited[r][c]) {
            return;
        }
        isVisited[r][c] = true;
        if (getSum(r) + getSum(c) > threshold) {
            return;
        }
        count++;
        //下
        helper(threshold, r + 1, c, isVisited);
        //上
        helper(threshold, r - 1, c, isVisited);
        //右
        helper(threshold, r, c + 1, isVisited);
        // 左
        helper(threshold, r, c - 1, isVisited);
    }

    public int getSum(int num) {
        String[] split = String.valueOf(num).split("");
        int sum = 0;
        for (String s : split) {
            sum += Integer.valueOf(s);
        }
        return sum;
    }

    /**
     * 得到各位数之和的正确方式
     * @param num
     * @return
     */
    public int getBitSum(int num){
        int sum=0;
        while (num!=0){
            sum+=num%10;
            num/=10;
        }
        return sum;

    }

    /**
     * 官方的方法
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public int movingCount2(int threshold, int rows, int cols) {
        boolean[][] v = new boolean[rows][cols];
        int count = core(threshold, rows, cols, 0, 0, v);
        return count;
    }

    public int core(int threshold,int rows,int cols,int r,int c,boolean[][] v){
        if (r<0||r>rows||c<0||c>cols||v[r][c]||getBitSum(r)+getBitSum(c)>threshold){
            return 0;
        }
        v[r][c]=true;
        return 1+core(threshold,rows,cols,r-1,c,v)
                +core(threshold,rows,cols,r+1,c,v)
                +core(threshold,rows,cols,r,c-1,v)
                +core(threshold,rows,cols,r,c+1,v);
    }


}
